package com.demo.图;

import com.demo.图.model.Edge;
import com.demo.图.model.Graph;
import com.demo.图.model.Vertex;

import java.util.List;
import java.util.Map;
import java.util.Objects;

/**
 * @author cl
 */
public class GraphConvert {

    /** 将邻接表转为自定义的图结构 无权重 */
    public static <T> Graph<T> adjacencyListConvertToGraph(Map<T, List<T>> adj) {
        Objects.requireNonNull(adj);
        Graph<T> graph = new Graph<>();
        for (Map.Entry<T, List<T>> entry: adj.entrySet()) {
            // 获取当前节点 没有就创建
            Vertex<T> vertex = graph.vertexMap.putIfAbsent(entry.getKey(), new Vertex<>(entry.getKey()));
            vertex = Objects.isNull(vertex) ? graph.vertexMap.get(entry.getKey()) : vertex;
            // 节点的出数目
            vertex.out = entry.getValue().size();
            /** 临节点处理 */
            for (T ver : entry.getValue()) {
                Vertex<T> toVertex = graph.vertexMap.putIfAbsent(ver, new Vertex<>(ver));
                toVertex = Objects.isNull(toVertex) ? graph.vertexMap.get(ver) : toVertex;
                vertex.addNext(toVertex);
                toVertex.in += 1;
                // 做边
                Edge<T> edge = null;
                for (Edge<T> tmpEdge : graph.edges) {
                    if (tmpEdge.from == vertex && tmpEdge.to == toVertex) {
                        edge = tmpEdge;
                        break;
                    }
                }
                if (edge == null) {
                    edge = new Edge<>(vertex, toVertex, 0);
                    graph.addEdge(edge);
                }
                // 节点添加关联边
                vertex.addEdge(edge);
            }
        }
        return graph;
    }

    /** 将邻接表转为自定义的图结构 有权重 */
    public static <T> Graph<T> adjacencyListConvertToGraphWithWeight(Map<T, List<List<T>>> adj) {
        Objects.requireNonNull(adj);
        Graph<T> graph = new Graph<>();
        for (Map.Entry<T, List<List<T>>> entry: adj.entrySet()) {
            // 获取当前节点 没有就创建
            Vertex<T> vertex = graph.vertexMap.putIfAbsent(entry.getKey(), new Vertex<>(entry.getKey()));
            vertex = Objects.isNull(vertex) ? graph.vertexMap.get(entry.getKey()) : vertex;
            // 节点的出数目
            vertex.out = entry.getValue().size();
            /** 临节点处理 */
            for (List<T> ver : entry.getValue()) {
                Vertex<T> toVertex = graph.vertexMap.putIfAbsent(ver.get(0), new Vertex<>(ver.get(0)));
                toVertex = Objects.isNull(toVertex) ? graph.vertexMap.get(ver.get(0)) : toVertex;
                vertex.addNext(toVertex);
                toVertex.in += 1;
                // 做边
                Edge<T> edge = null;
                for (Edge<T> tmpEdge : graph.edges) {
                    if (tmpEdge.from == vertex && tmpEdge.to == toVertex) {
                        edge = tmpEdge;
                        break;
                    }
                }
                if (edge == null) {
                    edge = new Edge<>(vertex, toVertex, (Integer) ver.get(1));
                    graph.addEdge(edge);
                }
                // 节点添加关联边
                vertex.addEdge(edge);
            }
        }
        return graph;
    }
}
